//题目:
// 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
// 请实现 KthLargest 类：
// KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
// int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;
//代码:
class KthLargest 
{
    // priority_queue<int> heap_big;
    priority_queue<int,vector<int>,greater<int>> heap_small;

    int _k;
    struct compare{
        bool operator()(int x,int y)
        {
            return x>y;//降序
        }
    };
public:
    KthLargest(int k, vector<int>& nums) 
    {
        _k=k;
        //插入nums中前K个最大的元素
        if(nums.size()>k) sort(nums.begin(),nums.end(),compare());
        for(int i=0;i<k && i<nums.size();i++)
        {
            heap_small.push(nums[i]);
        }
    }
    
    int add(int val) 
    {
        //解决_k小于size的情况
        if(heap_small.size()<_k)
        {
            heap_small.push(val);
            return heap_small.top();
        }
        //比较新插入的元素与原本第K大元素的大小，更新第前K大元素
        else if(val>heap_small.top())
        {
            heap_small.pop();
            heap_small.push(val);
            return heap_small.top();
        }
        return heap_small.top();
    }
};